package system2021.src.class01sortAndSearch;

/**
 * 局部最小值的问题
 */
public class Code06_BSAwesome {

    // null
    // 长度为0
    // 长度为1

    /**
     * 思路一：长度大于2，1
     * - 最左边的点作为最小值；最右边的点作为最小值
     * - 两个边界点都不是最小值
     * - 相等
     * - 向下弯曲
     * - mid大于某一边可以判断哪边存在最小值
     * - 都小于，和左、右比较
     * ...
     */
    // 可以看到我们思路一的实现比较精细和繁琐，比较难以实现
    // 这个时候就先尝试切换思路，直接通过和mid左右两个元素的值进行比较得出答案
    public static int getLessIndex(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1; // no exist
        }
        if (arr.length == 1 || arr[0] < arr[1]) {
            return 0;
        }
        if (arr[arr.length - 1] < arr[arr.length - 2]) {
            return arr.length - 1;
        }
        int left = 1;
        int right = arr.length - 2;
        int mid = 0;
        // left < right 为何这里的比较是 < 而不是 <=，其实和普通的搜索元素的逻辑不太一样
        // 普通搜索元素只需要和当前下标值进行比较，只需要用到数组中的一个元素
        // 这里是区间最小值，当我们搜索区间只有两个元素的时候就可以得到最后的答案
        while (left < right) {
            mid = (left + right) / 2;
            if (arr[mid] > arr[mid - 1]) {
                right = mid - 1;
            } else if (arr[mid] > arr[mid + 1]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return left;
    }
}
